洛谷 P5985 · 难度 提高+/省选−

题目描述

给定 $n$ 个整数 $a_{1..n}$，请找到 $n$ 个非负整数 $b_{1..n}$，使得 $a_1\times \mathrm{f}({\mathrm{b}}_1)+a_2\times \mathrm{f}({\mathrm{b}}_2)+...+a_n\times \mathrm{f}({\mathrm{b}}_{\mathrm{n}})$ 的值最大，其中 $\mathrm{f}(\mathrm{x})$ 为 $x$ 在二进制下的 $1$ 的个数。

你找到的这 $n$ 个非负整数 $b_{1..n}$ 需要满足 $0\le b_1<b_2<...<b_n\le m$。

输入格式

第一行两个整数 $n,m$。

第二行包含 $n$ 个整数 $a_1,a_2,...,a_n$。

输出格式

输出一行一个整数，即 $a_1\times \mathrm{f}({\mathrm{b}}_1)+a_2\times \mathrm{f}({\mathrm{b}}_2)+...+a_n\times \mathrm{f}({\mathrm{b}}_{\mathrm{n}})$ 的最大值。

说明/提示

对于 $100\mathrm{\%}$ 的数据，$1\le n\le 200$，$n-1\le m\le {10}^{18}$，$|a_i|\le {10}^{14}$。

---

解释：

$b_1=3,b_2=4,b_3=5$，则答案为 $2\times 2+(-1)\times 1+3\times 2=9$。

样例

样例 1

输入

3 5
2 -1 3

输出

9